package leetcode_jz_offer;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author 美女
 * @date 2022/08/29 18:21
 **/
public class Num40_最小的k个数 {
    public int[] getLeastNumbers(int[] arr, int k) {
        //优先级队列-topK问题，最小的k个数用到最大堆
        //最大堆包含k个元素，当存储到k后，再入的元素如果小于就将加入堆中，如果大于不加入继续遍历后面元素
        //最后堆中存储最小的k个元素
        //注意，JDK内部默认是最小堆的实现
        if(arr==null||k==0){
            return new int[0];
        }
        Queue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        });
        int[] res=new int[k];
        for(int i=0;i<arr.length;i++){
            if(i<k){
                queue.offer(arr[i]);
            }else{
                if(arr[i]>queue.peek()){
                    continue;
                }else{
                    //此时元素小于堆顶元素，取出堆顶元素（最大，大的先出），让该元素入队
                    queue.poll();
                    queue.add(arr[i]);
                }
            }
        }
        for(int i=0;i<k;i++){
            res[i]=queue.poll();
        }
        return res;
    }
}
